package LearnDataStructure.c_树结构.例题;

import LearnDataStructure.c_树结构.BSTNode;
import LearnDataStructure.c_树结构.有序树.二叉树.b_MyBinaryTreebyLinked;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-12 20:35
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.c_树结构.例题
 */
public class e_返回某一层所有节点以链表的结果 {
    public static void main(String[] args) {
        e_返回某一层所有节点以链表的结果 test = new e_返回某一层所有节点以链表的结果();
        b_MyBinaryTreebyLinked<Integer, Integer> binaryTree = new b_MyBinaryTreebyLinked<>();
        binaryTree.insert(6,6);
        binaryTree.insert(7,7);
        binaryTree.insert(4,4);
        binaryTree.insert(5,5);
        binaryTree.insert(8,8);
        binaryTree.insert(2,2);

        LinkedNodeTwoWay<Integer> linkedHead = test.getLayerFromTree(binaryTree.getRoot(), 2);

        System.out.println(binaryTree);

        while (linkedHead != null) {
            System.out.println(linkedHead.date);
            linkedHead = linkedHead.next;
        }
    }

    public LinkedNodeTwoWay<Integer> getLayerFromTree(BSTNode<Integer,Integer> root, int dep) {
        if (root == null) {
            return null;
        }
        if (dep == 1) {//如果要根节点，则判断是否存在root,上面已经判断了所以如果进行到这个if，那么一定root != null
            LinkedNodeTwoWay<Integer> result = new LinkedNodeTwoWay<Integer>(root.value);
            return result;
        }
        LinkedNodeTwoWay<Integer> head = null;
        LinkedNodeTwoWay<Integer> tail = null;
        Queue<NodeAndHeight> queue = new LinkedList<NodeAndHeight>();
        //root入队列
        queue.offer(new NodeAndHeight(root,1));//offer()是更安全的add(),当队列满的时候仍然添加，add报错offer返回false
        while (!queue.isEmpty()) {
            //执行“弹一个”------------------------------------------------------------
            NodeAndHeight pollElement = queue.poll();//poll()是更安全的pop()方法
            //完成“弹一个”------------------------------------------------------------

            //执行“入2个”------------------------------------------------------------
            if (pollElement.height == dep) {//就是目标行的元素
                if (head == null) {//这个只会执行一次
                    head = new LinkedNodeTwoWay<Integer>(pollElement.node.value);//生成头节点
                    tail = head;//尾节点也做好
                } else {
                    tail.next = new LinkedNodeTwoWay<Integer>(pollElement.node.value);
                    tail.next.pre = tail;
                    tail = tail.next;//移动尾指针
                }
            } else if (pollElement.height > dep) {//越过了目标行，代表目标行全部元素取出
                break;
            }
            if (pollElement.node.left != null && pollElement.height < dep) {
                queue.offer(new NodeAndHeight(pollElement.node.left, pollElement.height + 1));
                /*
                这里入队的高度必须+1，因为树！树的孩子child,child一定比父节点pollElement的层更深1层
                 */
            }
            if (pollElement.node.right != null && pollElement.height < dep) {
                queue.offer(new NodeAndHeight(pollElement.node.right, pollElement.height + 1));
            }
            //完成“入2个”------------------------------------------------------------
        }
        return head;
    }

    private class NodeAndHeight {
        public BSTNode<Integer,Integer> node = null;
        public int height = 0;//不是严格意义上的树高，而是层数

        public NodeAndHeight(BSTNode<Integer, Integer> node, int height) {
            this.node = node;
            this.height = height;
        }
    }
}
